给定一个值n,请生成所有的存储值1...n.的二叉搜索树(BST)的结构
例如:
给定n=3,你的程序应该给出下面五种不同的二叉搜索树(BST)
class Solution: def __init__(self): # 使用备忘录存储优化 self.memo = {} def generateTrees(self , n ): if n == 0: return [None] if n == 1: return [TreeNode(1)] # 使用数据范围做递归构树 result = self.built(1, n) # 返回所有结果 return result # 根据范围递归构树 def built(self, start, end): if start > end: return [None] if start == end: return [TreeNode(start)] # 查询是否在备忘录中 if (start, end) in self.memo: return self.memo[(start, end)] # 中间结果 mid = [] # 每个结点做根结点 for i in range(start, end+1): # 选定i作为根,再递归构造所有可能的左右子树 left = self.built(start, i-1) right = self.built(i+1, end) # 构造每一棵树 for l in left: for r in right: root = TreeNode(i) root.left = l root.right = r # 存结果 mid.append(root) # 备忘录存储 self.memo[(start, end)] = mid # 返回结果 return self.memo[(start, end)]